package lc_剑指_Offer_II_057_值和下标之差都在给定的范围内;

import java.util.TreeMap;

import algorithm.helper.impl.Converter;

public class Solution {

	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
		TreeMap<Long, Integer> tm = new TreeMap<>();
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			if (i > k) {
				long out = nums[i - k - 1];
				int res = tm.merge(out, -1, Integer::sum);
				if (res == 0) {
					tm.remove(out);
				}
			}
			Long l = tm.ceilingKey(1l * num - t);
			Long r = tm.floorKey(1l * num + t);
			if (r != null && l != null && l <= r) {
				return true;
			}
			tm.merge(1l * num, 1, Integer::sum);
		}
		return false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		boolean ans = so.containsNearbyAlmostDuplicate(Converter.instance().toIntArray("[1,5,9,1,5,9]"), 2, 3);
		System.out.println(ans);
	}
}